package woa.linkedlist;

/**
 * 单链表验证回文字符串问题
 * https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
 *
 * @author wangpeng
 */
public class PalindromeStringProblem {

    /**
     * 是否回文字符串
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeString(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        //找中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //后半部分链表反转
        ListNode reverse = reverseLinkedList1(slow);
        //比较前后部分是否相等
        fast = head;
        while (reverse != null) {
            if (fast.val != reverse.val) {
                return false;
            }
            fast = fast.next;
            reverse = reverse.next;
        }
        return true;
    }

    /**
     * 单链表反转
     * 遍历方式
     *
     * @param head
     */
    public static ListNode reverseLinkedList(ListNode head) {
        ListNode cur = head;
        ListNode prev = head;
        ListNode temp = null;
        while (cur != null && cur.next != null) {
            temp = cur.next;
            cur.next = cur.next.next;
            temp.next = prev;
            prev = temp;
        }
        head = temp;
        return head;
    }

    /**
     * 单链表反转
     * 头插法
     *
     * @param head
     * @return
     */
    public static ListNode reverseLinkedList1(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    /**
     * 单链表反转
     * 递归法
     *
     * @param head
     * @return
     */
    public static ListNode reverseLinkedList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode reverse = reverseLinkedList2(next);
        next.next = head;
        head.next = null;
        return reverse;
    }

    public static void main(String[] args) {
        ListNode head = ListNodeUtils.createByArray(new int[]{1});
        System.out.println(isPalindromeString(head));
    }
}
